package com.yohann.algorithm;

import java.util.Arrays;

/**
 * <p>
 * 斐波那契查找
 * </p>
 *
 * @author Yohann
 * @since 2021/1/2 14:17
 */
public class FibonacciSearch {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 8, 10, 89, 1000, 1234};
        System.out.println(fibonacciSearch(arr, 1234));
    }

    /**
     * 获取斐波那契数列
     *
     * @return 斐波那契数列
     */
    private static int[] getFibonacci() {
        int[] fib = new int[20];
        fib[0] = 1;
        fib[1] = 1;

        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        return fib;
    }

    private static int fibonacciSearch(int[] arr, int target) {
        int low = 0, high = arr.length - 1, k = 0, middle = 0;
        int[] fib = getFibonacci();

        //获取比数组长度大的 斐波那契分割数组下标
        while (arr.length > fib[k]) {
            k++;
        }

        //构造临时数组 个数与斐波那契数一致
        int[] temp = Arrays.copyOf(arr, fib[k]);
        //超过部分用最后一个数填充
        for (int i = arr.length; i < temp.length; i++) {
            temp[i] = arr[high];
        }

        //开始搜寻
        while (low <= high) {
            //中间索引 左索引加斐波那契数
            middle = low + fib[k - 1] - 1;

            /*
            向左查询使用k-1斐波那契数
            向右查询使用k-2斐波那契数
            由此得到fib[k] = fib[k-1] + fib[k-2]
             */
            //向左查找
            if (target < temp[middle]) {
                //右索引
                high = middle - 1;
                //斐波那契数列索引
                k--;
            } else if (target > temp[middle]) {
                low = middle + 1;
                k -= 2;
            } else {
                //寻找到目标值 返回小的下标
                return middle < high ? middle : high;
            }
        }

        return -1;
    }
}